// @algorithm @lc id=100287 lang=cpp
// @title shu-de-zi-jie-gou-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode *A, TreeNode *B) {
        if (B == nullptr) {
            return false;
        }
        if (A == nullptr) {
            return false;
        }
        if (A->val != B->val) {
            return isSubStructure(A->left, B) || isSubStructure(A->right, B);
        }
        if (A->val == B->val) {
            if (B->left && B->right) {
                return isSubStructure(A->left, B) || isSubStructure(A->right, B) ||
                       (helper(A->left, B->left) && helper(A->right, B->right));
            }
            else if (B->left) {
                return isSubStructure(A->left, B) || isSubStructure(A->right, B) || helper(A->left, B->left);
            }
            else if (B->right) {
                return isSubStructure(A->left, B) || isSubStructure(A->right, B) || helper(A->right, B->right);
            }
            else {
                return true;
            }
        }
        return false;
    }

    bool helper(TreeNode *A, TreeNode *B) {
        if (B == nullptr) {
            return true;
        }
        if (A == nullptr) {
            return false;
        }
        if (A->val == B->val) {
            return helper(A->left, B->left) && helper(A->right, B->right);
        }
        else {
            return false;
        }
        return true;
    }
};